package datastructure.book.tujiesuanfa.queueastack.bean;

import java.util.PriorityQueue;

/**
 * 有序整数列表中的中间值,如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值
 */
public class MedianFinder {

    private PriorityQueue<Integer> leftQueue = new PriorityQueue<>((o1, o2) -> o2-o1);
    private PriorityQueue<Integer> rightQueue = new PriorityQueue<>();

    public MedianFinder() {

    }

    /**
     * 列表插入一个值
     */
    public void addNum(int num) {
        if (leftQueue.size() != rightQueue.size()) {
            leftQueue.add(num);
            rightQueue.add(leftQueue.poll());
        }else {
            rightQueue.add(num);
            leftQueue.add(rightQueue.poll());
        }
    }

    /**
     * 返回列表排序后的中位数
     */
    public double findMedian() {
        if (leftQueue.size() != rightQueue.size()) {
            return leftQueue.peek() == null ? -1 : leftQueue.peek();
        } else {
            Integer peek = leftQueue.peek();
            Integer peek1 = rightQueue.peek();
            if (peek1 == null || peek == null) {
                return -1;
            }
            return (double) (peek1+peek)/2;
        }
    }
}
